\documentclass{ctexart}
\usepackage{pgfplots}
\usepackage{float}%解决图片乱跑问题
\usepackage{geometry}%设置页面大小边距等
\usepackage{authblk}%作者机构等信息
\usepackage{graphicx}%插入图片
\usepackage{amssymb}%为了用\mathbb
\usepackage{amsmath}%数学方程的显示
\usepackage{listings}%插入代码
\usepackage{fancyhdr}%设置页眉页脚
\usepackage{lastpage}%总页数
\usepackage{tikz}
\usepackage{listings}%插入代码
\usepackage{hyperref}%引用网页
\usepackage{xcolor}%实现代码颜色高亮
\geometry{a4paper,left=2cm,right=2cm,top=2cm,bottom=2cm}%一定要放在前面！
\lstset{frame=single,basicstyle=\ttfamily,columns=flexible,language={C},
keywordstyle=\bf\color{blue},
commentstyle=\it\color[RGB]{0,96,96},
numberstyle=\color[RGB]{0,192,192}}


\pagestyle{fancy}%设置页眉页脚
\lhead{陈冠宇\ 3200102033}%页眉左
\chead{Numerical Analysis}%页眉中
\rhead{HW5 for theoretical questions}%章节信息
\cfoot{\thepage/\pageref{LastPage}}%当前页，记得调用前文提到的宏包
\rfoot{School of Mathematical Sciences in ZJU}
\renewcommand{\headrulewidth}{0.1mm}%页眉线宽，设为0可以去页眉线
\renewcommand{\footrulewidth}{0.1mm}%页脚线宽，设为0可以去页眉线
\setlength{\headwidth}{\textwidth}

\newtheorem{theorem}{Theorem}
\newtheorem{proof}{Proof}
\newtheorem{solution}{Solution:}
\newtheorem{remark}{Remark}

\hypersetup{%设置网页链接颜色等
    colorlinks=true,%链接将会有颜色，默认是红色
    urlcolor=blue,%链接到网站的链接将会变为蓝绿色（cyan）
    }

\title{Theoretical questions of Chapter3}
\everymath{\displaystyle}
\begin{document}
\section*{Theoretical questions of Chapter3}
\subsection*{\uppercase\expandafter{\romannumeral1}}
result: $(477)_{10}=(111011101)_2$.

\subsection*{\uppercase\expandafter{\romannumeral2}}
result: $\frac{3}{5}=(0.10011001\cdots)_2=(1.0011001\cdots)_2$.

\subsection*{\uppercase\expandafter{\romannumeral3}}
\begin{proof}
  Suppose the precision is p. Since $x=\beta ^e=1.00\cdots 0\times \beta^e$, then $x_L = (\beta-1).(\beta - 1)(\beta - 1)\cdots (\beta - 1)\times \beta ^{e-1}$ and $x_R = \beta^e+\beta^{e-p}$.

  Then $x_R-x=\beta^{e-p}=\beta (x-x_L)$
\end{proof}
\subsection*{\uppercase\expandafter{\romannumeral4}}
\begin{solution}
By $\romannumeral2$ we have
  $\frac{3}{5} = (1.0011001\cdots )_2 \times 2^{-2}$

  Under the IEEE 754 single-precision protocol, $\beta = 2, p = 23 +1, e\in [-126,127]$
  then we have $x_L = (1.0011001\cdots 011)_2 \times 2^{-1}$ and $x_R = (1.0011001\cdots 101)_2 \times 2^{-1}$

  Since $x-x_L = \frac{3}{5}\times 2^{-24}> x_R-x=\frac{2}{5}\times 2^{-24}$, then $fl(x) = x_R$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral5}}
\begin{solution}
 The unit roundoff will be $2^{-23}$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral6}}
\begin{solution}

$\cos \left(\frac{1}{4}\right)=(1.1111000000010 \cdots)_{2} * 2^{-1}$

Therefore by using Theorem  4.49,$2^{-6}<1-\frac{y}{x}<2^{-5}$

Therefore 5 to 6 bits of presiction are lost.
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral7}}
\begin{solution}
  (1)using Taylor expansion, then $1-cos(x)=\frac{x^2}{2!}-\frac{x^4}{4!}\cdots $

  (2)use the fact that $1-\cos x=2sin^2(\frac{x}{2})$
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral8}}
\begin{solution}
  1.$f(x) =  (x-1)^\alpha$, then $f'(x)=\alpha (x-1)^{\alpha - 1}$

  Hence $$C_f(x)=\left|\frac{xf'(x)}{f(x)}\right|=\left|\frac{\alpha x}{x-1}\right|\rightarrow \infty, x\rightarrow 1$$

  2.$f(x)=ln(x)$, then $f'(x)=\frac{1}{x}$

  Hence $$C_f(x)=\left|\frac{xf'(x)}{f(x)}\right|=\left|\frac{1}{ln(x)}\right|\rightarrow \infty, x\rightarrow 1$$

  3.$f(x)=e^x$, then $f'(x)=e^x$

  Hence $$C_f(x)=\left|\frac{xf'(x)}{f(x)}\right|=\left|x\right|\rightarrow \infty, x\rightarrow \infty$$

  4.$f(x)=arccos(x)$, then $f'(x)=-\frac{1}{\sqrt{1-x^2}}$

  Hence $$C_f(x)=\left|\frac{xf'(x)}{f(x)}\right|=\left|\frac{x}{\sqrt{1-x^2}arccos(x)}\right|\rightarrow \infty, x\rightarrow \pm 1$$

\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral9}}
\begin{solution}
  1.$f(x) =  1-e^{-x}$, then $f'(x)=e^{-x}$

  Hence $$C_f(x)=\left|\frac{xf'(x)}{f(x)}\right|=\left|\frac{x}{e^x-1}\right|$$

  Consider $g(x)=\frac{x}{e^x-1}$, then $g$ is monotonic decrement and $\lim_{x\rightarrow 0}g(x) = \lim_{x\rightarrow 0}\frac{1}{e^x} = 1$.
  That is $\left|C_f(x)\right|\leq 1,x \in [0,1]$.

  2.By definition 4.74, $cound_A(x)\frac{1}{\epsilon _u}inf\frac{||x_A-x||}{||x||}$.

  Since $|f(x)-f_A(x)|=|f(x)-f(x_A)|=|f'(\xi)||x-x_A|\leq e^x\epsilon_u$, then $cound_A(x)\leq \frac{e^x}{|x|}$

  3.Plots:
  \begin{figure}[!ht]
  \centering
	\begin{tikzpicture}
\begin{axis}[axis x line = middle,
                 axis y line = middle,
                 xmin=-1,xmax=12,
                 ymin=-1,ymax=8]
    \addplot[domain=-1:10,color=orange,very thick,smooth] {x/(e^x-1)};
    \addplot[domain=0.15:10,color=black,very thick,smooth] {e/x};
    
    \end{axis}
	\end{tikzpicture}
	\end{figure}
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral10}}
\begin{solution}

  (1)By definition, the componentwise condition number $cond_f(x)=||M(x)||$, where the $M(x)=[m_{ij}(x)]$ and $m_{ij}(x)=\left|\frac{x_j\frac{\partial f_i}{\partial x_j}}{f_i(x)}\right|$.

  Let $x=(a_0,a_1,\cdots, a_{n-1})'$, then $\frac{\partial f}{\partial a_{j-1}}=\frac{\partial f}{\partial q}*\frac{\partial q}{\partial a_{j-1}}=\frac{\partial q}{\partial a_{j-1}}/\frac{\partial q}{\partial f}=\frac{r^{j-1}}{q'(r)}$

  Hence
  $$\begin{aligned}
  m_{1j}&=\left|\frac{a_{j-1}\frac{\partial f}{\partial a_{j-1}}}{f(x)}\right|\\
  &=\left|\frac{a_{j-1}r^{j-2}}{q'(r)} \right|
  \end{aligned}$$

  (2)About Wilkinson example:

  $f(x)=\Pi_{k=1}^p(x-k)$, That is $q(r)=\Pi_{i=1}^n(r-i)$. then we have $q'(n)$ and $q'(r)$. Hence we have $cond_fA\geq n^{n-1}$.
  
  Therefore, the conditional number is huge, which is ill, leading to catastrophic cancellation.

\end{solution}

\subsection*{\uppercase\expandafter{\romannumeral11}}
\begin{solution}
In the FPN system  $(2,2,-1,1), a=1.0 \times 2^{0}, b=1.1 \times 2^{0} $. Then  $\frac{a}{b}=0.101010101 \cdots $, in a register of precision  4, $\frac{a}{b}=0.101$ , so  $fl\left(\frac{a}{b}\right)=1.0 \times 2^{-1}$  and  $E_{r e l}\left(\frac{a}{b}\right)=0.01=\epsilon_{u} $, which is contradictory to the model of arithmetic.
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral12}}
\begin{solution}
  Since the single precision FPNs of IEEE 754, we have $\beta = 2, p = 23+1$. Then $128 = (1.00\cdots 0)_2\times 2^7$ and $129 = (1.000000100\cdots)_2\times 2^7$.

  Then through bisection method, the final length is $2^{-23}\times 2^7=2^{-16}$. That is the final error is $0.5*2^{-16}=7.63\times 10^{-6}>10^{-6}$

  Hence we can't compute the root with absolute accuracy $< 10−6$.
\end{solution}
\subsection*{\uppercase\expandafter{\romannumeral13}}
\begin{solution}
Assume $f(x)=ax^3+bx^2+cx+d,f'(x)=3ax^2+2bx+c$, let$x_i,x_{i+1}$ we have to solve
$$\left(\begin{array}{cccc}
x_{i}^{3} & x_{i}^{2} & x_{i} & 1 \\
x_{i+1}^{3} & x_{i+1}^{2} & x_{i+1} & 1 \\
3 x_{i}^{2} & 2 x_{i} & 1 & 0 \\
3 x_{i+1}^{2} & 2 x_{i+1} & 1 & 0
\end{array}\right)\left(\begin{array}{l}
a \\
b \\
c \\
d
\end{array}\right)=\left(\begin{array}{c}
f\left(x_{i}\right) \\
f\left(x_{i+1}\right) \\
f^{\prime}\left(x_{i}\right) \\
f^{\prime}\left(x_{i+1}\right)
\end{array}\right)
$$

Let $$A=\left(\begin{array}{cccc}
x_{i}^{3} & x_{i}^{2} & x_{i} & 1 \\
x_{i+1}^{3} & x_{i+1}^{2} & x_{i+1} & 1 \\
3 x_{i}^{2} & 2 x_{i} & 1 & 0 \\
3 x_{i+1}^{2} & 2 x_{i+1} & 1 & 0
\end{array}\right)$$

Then the condition number of A is large because $x_i$ is close to $x_{i+1}$. So the result is inaccurate.
\end{solution}
\end{document}
